We present the first ab initio coupled-cluster calculations of medium-mass nuclei with explicit chiral three-nucleon (3N) interactions. Using a spherical formulation of coupled cluster with singles and doubles excitations including explicit 3N contributions, we study ground states of 16,24-O, 40,48-Ca and 56-Ni. We employ chiral NN plus 3N interactions softened through a similarity renormalization group (SRG) transformation at the three-body level. We investigate the impact of all truncations and quantify the resulting uncertainties---this includes the contributions from triples excitations, the truncation of the set of three-body matrix elements, and the omission of SRG-induced four-body interactions. Furthermore, we assess the quality of a normal-ordering approximation of the 3N interaction beyond light nuclei. Our study points towards the predictive power of chiral Hamiltonians in the medium-mass regime.